/*
 * @Author: 缄默
 * @Date: 2021-11-10 19:28:04
 * @LastEditors: 缄默
 * @LastEditTime: 2021-11-10 20:11:20
 */

//调整二叉搜索树中两个错误的节点

#include <iostream>
#include <vector>
#include <stack>
#include "../../DataStructure/tree.hpp"

using namespace std;

vector<int> getTwoErr(TreeNode* head);

int main() {
    vector<int> preOrder({2, 4, 1, 3, 6, 5, 7});
    vector<int> inOrder({1, 4, 3, 2, 5, 6, 7});
    TreeNode* head = buildTree(preOrder, inOrder, 0, 0, preOrder.size() - 1);
    vector<int> num = getTwoErr(head);
    for (auto i : num) {
        cout << i << endl;
    }
    return 0;
}

//非递归实现先序遍历
vector<int> getTwoErr(TreeNode* head) {
    vector<int> res(2, 0);
    if (head == nullptr) return res;
    stack<TreeNode*> node;
    TreeNode* pre = new TreeNode();
    while (!node.empty() || head != nullptr) {
        if (head != nullptr) {
            node.push(head);
            head = head->left;
        }
        else {
            head = node.top();
            node.pop();
            if (pre != nullptr && pre->val > head->val) {
                //实现第一次下降较大值和第二次下降较小值
                res[0] = res[0] == 0 ? pre->val : res[0];
                res[1] = head->val;
            }
            pre = head;
            head = head->right;
        }
    }
    return res;
}